package first
/*
	给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

	单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

	 

	例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。



	 

	示例 1：

	输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
	输出：true
	示例 2：

	输入：board = [["a","b"],["c","d"]], word = "abcd"
	输出：false
	 

	提示：

	1 <= board.length <= 200
	1 <= board[i].length <= 200
	board 和 word 仅由大小写英文字母组成

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/ju-zhen-zhong-de-lu-jing-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
func Exist(board [][]byte, word string) bool {
	return exist(board, word)
}
func exist(board [][]byte, word string) bool {
	used := make([][]bool, len(board))
	for i := 0; i < len(board);i++ {
		used[i] = make([]bool, len(board[i]))
	}
	for i := 0; i <len(board);i++ {
		for j := 0; j < len(board[i]);j++ {
			if _exist(board, word,"", used, i, j){
				return true
			}
		}
	}
	return false
}

func _exist(board [][]byte, word string, cur string, used [][]bool, start_row, start_col int) bool {
	if start_row < 0 || start_row >= len(board) || start_col < 0 || start_col >= len(board[start_row]) {
		return false
	}
	if len(word) == 0 {
		return false
	}
	if used[start_row][start_col] {
		return false
	}
	if word[0] == board[start_row][start_col] && len(word)==1 {
		return true
	}

	if word[0] == board[start_row][start_col] {
		used[start_row][start_col] = true
		result :=  _exist(board, word[1:],cur+string(word[0]), used, start_row-1, start_col)||
			_exist(board, word[1:],cur+string(word[0]), used, start_row, start_col+1)||
			_exist(board, word[1:],cur+string(word[0]), used, start_row+1, start_col)||
			_exist(board, word[1:],cur+string(word[0]), used, start_row, start_col-1)
		used[start_row][start_col] = false // backtrace
		return result
	}

	return false
}